In automated control environments, such as industrial robotic systems, synchronization objects may be utilized by one or more control programs, and controlling and synchronizing access and utilization of the synchronization objects typically requires complex and error prone programming to interface the synchronization object and the control programs. Moreover, in conventional systems, the types of synchronization objects encountered in a typical industrial robotic system varies, which increases complexity and leads to errors in programming the interfaces for each synchronization object.
As automated control environments become more advanced and complex, the number of synchronization objects and control programs increases. In conventional systems, the advancements have led to increased difficulty in synchronizing the control programs and the synchronization objects. In automated control environments, synchronization objects may be of different types, where the type of synchronization object dictates how control programs may interact and utilize the synchronization object. The types of synchronization objects typically present in an automated control environment include mutex, rendezvous, barrier, buffer, fixture, handoff, sequence element, multi-sequence element, and time synchronization.
A mutex type synchronization object allows only one control program to utilize the synchronization object at a time. In automated control environments, such as industrial robotic systems, for example, a mutex synchronization object may allow only one robot control program to enter and utilize the synchronization object, while making another control program wait, which may be useful, for example, for preventing robots from colliding, etc.
A rendezvous type synchronization object requires two control programs to “rendezvous” or wait for each other to acquire the synchronization object, at which time both will release the synchronization object and proceed. (Note: rendezvous does NOT necessarily mean concurrent execution, but only simultaneous presence at a point in the control programs.) In automated control environments, such as industrial robotic systems, for example, a rendezvous synchronization object may require a first control program to wait for a second control program at a predefined location, or meeting point, such that when both control programs “arrive” at the location, the two programs may then proceed. A barrier type synchronization object is an extended form of rendezvous, where more than two control programs meet at a predefined location before proceeding. In conventional systems, a counter associated with the barrier synchronization object increments when a control program arrives, and when the counter reaches a predefined value, the barrier synchronization object allows the control programs to proceed.
A buffer type synchronization object differentiates control programs by what action the control program will execute while utilizing the buffer. A producer control program will place items in a buffer, and a consumer control program will remove items from the buffer. For example, in industrial robotic systems, a first control program may execute to place parts in a buffer, and a second control program may execute to remove parts from the buffer. A buffer synchronization object typically allows only one control program to utilize the buffer at a time, and also limits utilization by consumers and producers depending on whether the buffer is empty or full.
A fixture type synchronization object is a special form of buffer with a capacity of one, hence a consumer is allowed to utilize the fixture only if a producer has previously deposited an item at the fixture, and similarly, a producer is allowed to utilize the fixture only if there is not an item already deposited at the fixture. For example, in industrial robotic systems, a fixture synchronization object may be designed to facilitate transfer of parts among robots.
A handoff type synchronization object facilitates transfer of items among control programs. For example, in industrial robotic systems, a handoff facilitates transfer of a part from one robot to another robot without the need for a buffer or fixture. Hence, in contrast to a buffer or fixture, a handoff type synchronization object typically requires more than one control program to concurrently execute within the handoff synchronization object to enable the transfer.
A sequence element type synchronization object is a form of a barrier in which all control programs do not have to wait for others to arrive. A sequence element does not require control programs to be simultaneously present; however, all control programs must pass the synchronization object. In addition, a sequence element differentiates between control programs into signaling and waiting control programs, where a signaling control program must merely signal that it has passed the synchronization object, while a waiting control program must wait for all signalers to pass. In conventional systems, a counter associated with the sequence element is incremented when a signaler passes or a waiter arrives, and when the counter reaches a predefined number, the waiters are allowed to proceed.
Multi-sequence elements are essentially a group of related sequence elements which generally involve the same set of control programs, and wherein each sequence element may have different signaling and waiting control programs. A counter may be used for each element, and may re-initialize and reset count between elements. Like a hand-off, a multi-sequence element can be used to synchronize several steps between control programs coordinating for common procedure or to interface with a single component.
A time synchronization object forces parallel execution of control programs. In industrial robotic systems, a time synchronization object is commonly used to coordinate motion execution among robots controlled by different control program threads.
Examples of automated systems utilizing mutex objects to synchronize program execution can be found in U.S. Pat. No. 7,144,147 to Chafee et al. entitled “System controlling exclusive access by control programs to system resources”. Examples of automated systems utilizing barrier objects can be found in U.S. Pat. No. 7,024,250 to Graf et al. entitled “Method and apparatus for the synchronous control of manipulations”.
The difficulties and complexities encountered in designing and operating environments incorporating a plurality of the above described synchronization objects and having a plurality of control programs may lead to deadlock of control programs. As those skilled in the art will recognize, a mutex deadlock is a situation where two or more control programs are each waiting for another control program to begin and/or complete utilization of a shared resource in a circular chain, such that each control program may never begin and/or complete utilization. A deadlock may typically be identified if four conditions, known as “Coffman Conditions,” for the mutex objects are met: (1) mutual exclusion—a shared resource cannot be used by more than one control program at a time (this is the definition of a “mutex” object); (2) hold and wait—control programs already holding a resource may request new resources; (3) no preemption—no resource can be forcibly removed from a control program holding it; and (4) circular wait—two or more control programs form a circular chain where each control program waits for a resource that the next control program in the chain holds. Deadlocks related to resource sharing are particularly common in multiprocessing, where two or more control programs may share a mutex type synchronization object.
But there are also deadlocks related to combinations of all the above mentioned synchronization objects, not just those associated with mutex objects. These deadlocks are particularly troublesome, because analysis, detection, prevention etc. based only on Coffman Conditions related to mutex objects is insufficient.
In automated control environments, such as industrial robotic systems, deadlock of control programs can lead to halts in production and require significant time to determine the cause of the deadlock and attempt to resolve the deadlock. Moreover, in many automated control environments, it can be difficult or impossible to “unwind” a system sufficiently to eliminate a deadlock without the waste of expensive components or the expenditure of significant time. In some cases, significant manual operation of components of the system may be necessary to solve a deadlock, and additional errors may occur while the system is not functioning according to its automated programming.
In control environments that regularly operate on a set schedule, control programs may run hundreds or thousands of times without resulting in a deadlock before an alteration of the timing in one or more of the programs results in a previously undetected deadlock. In many automated systems, deadlocks have historically been detected and corrected through trial and error. It is costly to design, build, and install industrial machines that may not, when activated, successfully work together as intended.
Consequently, there is a continuing need in the art for a way to detect deadlocks after they occur, known in the art as deadlock detection. There is also a need in the art to find ways to predict and circumvent deadlocks during execution of control programs, known in the art as deadlock avoidance. And finally, there is a continuing need in the art to detect potential deadlocks among control programs during design time, before the programs are executed, known in the art as deadlock prevention. Many of the techniques in the art for avoidance are not practical in industrial applications. For example, while we can back up or unwind an airline reservation to avoid a deadlock, we cannot usually unwind production of products in factories. This invention is therefore related to detection and prevention of deadlocks among control programs that include any combination of synchronization object types.